!not sovled
package com.xinpan.exercise;

import java.util.HashMap;
import java.util.Map;


public class InPostConstructTree {
	
	public TreeNode buildTree(int[] inorder, int[] postorder) 
	{
        // Start typing your Java solution below
        // DO NOT write main() function
        if(inorder.length == 0)
            return null;
        
            
        Map<Integer, Integer> valPosMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < inorder.length; i++)
        {
             valPosMap.put(inorder[i], i);
        }
           
        int pos =  postorder.length - 1;
        int val = postorder[pos];
        TreeNode root = new TreeNode(val);
        
        int div = valPosMap.get(val);
        root.left = findRoot(0, div-1, inorder, postorder, pos-1, valPosMap);
        root.right = findRoot(div+1, pos, inorder, postorder, pos-1-div, valPosMap);
        
        return root;
    }
    
    public TreeNode findRoot(int s, int e, int[] inorder, int[] postorder, int pos, Map<Integer, Integer> valPosMap)
    {
        if(e < s)
            return null;
        else if(e == s)
        {
            int val = inorder[s];
            return new TreeNode(val);
        }
        
        int val = postorder[pos];
        TreeNode root = new TreeNode(val);
        
        int div = valPosMap.get(val);
        root.left = findRoot(s, div-1, inorder, postorder, pos-1, valPosMap);
        root.right = findRoot(div+1, e, inorder, postorder, pos-1-(div-s), valPosMap);
        
        return root;
    }
	/*
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(inorder.length == 0)
            return null;
        
        List<Integer> inList = new ArrayList<Integer>();
        for(int in : inorder)
            inList.add(in);
        Map<Integer, Integer> valPosMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < postorder.length; i++)
            valPosMap.put(postorder[i], i);
            
        int val = postorder[postorder.length-1];
        TreeNode root = new TreeNode(val);
        
        int pos = inList.indexOf(val);
        root.left = findRoot(inList.subList(0, pos), valPosMap);
        root.right = findRoot(inList.subList(pos+1, inList.size()), valPosMap);
        
        return root;
    }
    
    public TreeNode findRoot(List<Integer> inList, Map<Integer, Integer> valPosMap)
    {
        if(inList.size() == 0)
            return null;
        else if(inList.size() == 1)
        {
            int val = inList.get(0);
            return new TreeNode(val);
        }
        
        int inPos = -1;
        int lastPos = -1;
        for(int i = 0; i < inList.size(); i++)
        {
            int pos = valPosMap.get(inList.get(i));
            if(pos > lastPos)
            {
                lastPos = pos;
                inPos = i;
            }
        }
        
        TreeNode root = new TreeNode(inList.get(inPos));
        root.left = findRoot(inList.subList(0, inPos), valPosMap);
        root.right = findRoot(inList.subList(inPos+1, inList.size()), valPosMap);
        
        return root;
    }*/
    
    
    class TreeNode 
    {
      	 int val;
      	 TreeNode left;
      	 TreeNode right;
      	 TreeNode(int x) { val = x; }
    }
    
    
    public static void main(String[] args)
    {
    	InPostConstructTree ipct = new InPostConstructTree();
    	int[] in = {1,3,2};
    	int[] post = {3,2,1};
    	ipct.buildTree(in, post);
    }
}
